
// leetcode 22. 括号生成
//class Solution {
//    public List<String> generateParenthesis(int n) {
//        generateParenthesis(n, 0, 0, 0);
//        return ret;
//    }
//
//    // leftCount 是左括号的总个数
//    // rightCount 是右括号的总个数
//    List<String> ret = new ArrayList<>();
//    StringBuilder path = new StringBuilder();
//
//    public void generateParenthesis(int n, int index, int leftCount, int rightCount) {
//        // path 的长度一定是 2*n
//        if (index == 2 * n) {
//            ret.add(new String(path));
//            return;
//        }
//        // 左括号小于 n，就添加左括号
//        if (leftCount < n) {
//            path.append('(');
//            generateParenthesis(n, index + 1, leftCount + 1, rightCount);
//            path.delete(path.length() - 1, path.length());
//        }
//        // 如果左括号数量大于右括号，说明需要添加右括号了(目标是左括号数量与右括号数量一致)
//        if (leftCount > rightCount) {
//            path.append(')');
//            generateParenthesis(n, index + 1, leftCount, rightCount + 1);
//            path.delete(path.length() - 1, path.length());
//        }
//    }
//}


// leetcode 79. 单词搜索
//class Solution {
//    public boolean exist(char[][] board, String word) {
//        int m = board.length;
//        int n = board[0].length;
//        boolean ret = false;
//        boolean[][] flg = new boolean[m][n];
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (dfs(board, flg, i, j, m, n, word, 0)) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    public boolean dfs(char[][] board, boolean[][] flg, int i, int j, int m, int n, String word, int index) {
//        if (index == word.length())
//            return true;
//        if (i < 0 || i >= m || j < 0 || j >= n || flg[i][j])
//            return false;
//        char ch = word.charAt(index);
//        if (ch == board[i][j]) {
//            flg[i][j] = true;
//            boolean flg1 = dfs(board, flg, i - 1, j, m, n, word, index + 1);
//            boolean flg2 = dfs(board, flg, i + 1, j, m, n, word, index + 1);
//            boolean flg3 = dfs(board, flg, i, j - 1, m, n, word, index + 1);
//            boolean flg4 = dfs(board, flg, i, j + 1, m, n, word, index + 1);
//            flg[i][j] = false;
//            return flg1 || flg2 || flg3 || flg4;
//        } else {
//            return false;
//        }
//    }
//}


// leetcode 131. 分割回文串
//class Solution {
//
//    public List<List<String>> partition(String s) {
//        partition(s, 0);
//        return ret;
//    }
//
//    List<List<String>> ret = new ArrayList<>();
//    List<String> path = new ArrayList<>();
//
//    // 递归切割
//    public void partition(String s, int index) {
//        if (index > s.length())
//            return;
//        if (index == s.length()) {
//            // 当切割的下标为 s 字符串的长度时，说明已经切割完了
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        for (int i = index; i < s.length(); i++) {
//            // 切割的子串：[index, i]
//            String str = s.substring(index, i + 1);
//            // 判断是否是回文字符串，如果是，才添加
//            if (judge(str)) {
//                path.add(str);
//                partition(s, i + 1);
//                path.remove(path.size() - 1);
//            }
//        }
//    }
//
//    // 判断是否是回文字符串
//    public boolean judge(String str) {
//        int left = 0, right = str.length() - 1;
//        while (left < right) {
//            if (str.charAt(left) != str.charAt(right)) {
//                return false;
//            }
//            left++;
//            right--;
//        }
//        return true;
//    }
//}


// leetcode 51. N 皇后
//class Solution {
//    public List<List<String>> solveNQueens(int n) {
//        // 用二维数组比较方便
//        char[][] arr = new char[n][n];
//        // 初始化
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                arr[i][j] = '.';
//            }
//        }
//        solveNQueens(n, 0, arr);
//        return ret;
//    }
//
//    // 三维数组
//    List<List<String>> ret = new ArrayList<>();
//    // 二维数组，用来记录搜索的路径的
//    List<String> path = new ArrayList<>();
//
//    public void solveNQueens(int n, int index, char[][] arr) {
//        if (index == n) {
//            // 说明遍历完了，添加结果集
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        // 行固定是 index
//        for (int i = 0; i < n; i++) {
//            if (isQueen(arr, index, i, n)) {
//                // 是合法的女皇
//                arr[index][i] = 'Q';
//                path.add(new String(arr[index]));
//                // 去下一行挑选元素成为女皇
//                solveNQueens(n, index + 1, arr);
//                path.remove(path.size() - 1);
//                arr[index][i] = '.';
//            }
//        }
//    }
//
//    public boolean isQueen(char[][] arr, int i, int j, int n) {
//        // 判断当前女皇的这一行，这一列，左右对角线上是否有女皇
//        // 记录女皇数量
//        int count = 0;
//        // 这一行
//        for (int k = 0; k < n; k++) {
//            if (arr[i][k] == 'Q') {
//                return false;
//            }
//        }
//        // 这一列
//        for (int k = 0; k < n; k++) {
//            if (arr[k][j] == 'Q') {
//                return false;
//            }
//        }
//        // 对角线 （2， 0） n = 4
//        // 反对角线 (1, 1) (0, 2)   sum = i + j
//        // 正对角线 (3, 1) (x - i) == (y - j)
//        int sum = i + j;
//        for (int x = 0; x < n; x++) {
//            for (int y = 0; y < n; y++) {
//                if (x + y == sum && arr[x][y] == 'Q') {
//                    return false;
//                }
//                if ((x - i) == (y - j) && arr[x][y] == 'Q') {
//                    return false;
//                }
//            }
//        }
//        return true;
//    }
//}


// leetcode 35. 搜索插入位置
//class Solution {
//    public int searchInsert(int[] nums, int target) {
//        int left = 0, right = nums.length - 1;
//        while (left <= right) {
//            int mid = (left + right) / 2;
//            if (nums[mid] < target) {
//                left = mid + 1;
//            } else if (nums[mid] > target) {
//                right = mid - 1;
//            } else {
//                return mid;
//            }
//        }
//        return left;
//    }
//}


// leetcode 74. 搜索二维矩阵
//class Solution {
//    public boolean searchMatrix(int[][] matrix, int target) {
//        int m = matrix.length, n = matrix[0].length;
//        int x = 0, y = n - 1;
//        while (x < m && y >= 0) {
//            int cur = matrix[x][y];
//            if (cur < target) {
//                x++;
//            } else if (cur > target) {
//                y--;
//            } else {
//                return true;
//            }
//        }
//        return false;
//    }
//}